package com.zsj.Tree;

import java.util.*;

/**
 * @Author zsj
 * @Version 1.0
 * @Date 2024/4/13 13:38
 * @Description 非递归方法实现二叉树遍历(迭代)
 */
public class TreeTraversal {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1
                , new TreeNode(2, new TreeNode(4), new TreeNode(7)),
                new TreeNode(3, new TreeNode(5), new TreeNode(6)));
        preorderTraversal(root).forEach(System.out::println);
        System.out.println("===");
        inorderTraversal(root).forEach(System.out::println);
        System.out.println("===");
        postTraversal(root).forEach(System.out::println);
        System.out.println("===");
        modelTraversal(root);
        TreeNode curr = root;//当前节点
        /*
        想要遍历所有的节点(绕树一周)  有一个难点是  需要知道来时的路 或者说当前节点的父节点是谁
        想解决这个难点 我们可以使用一种数据结构来解决  《栈》
        */
        LinkedList<TreeNode> stack = new LinkedList<>();
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                System.out.print("去:" + curr.val + "\t");
                stack.push(curr);//记住回来的路
                curr = curr.left;
            } else {
                TreeNode pop = stack.pop();
                System.out.print("回:" + pop.val + "\t");
                curr = pop.right;
            }
        }

    }

    //前序遍历
    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                result.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode pop = stack.pop();
                cur = pop.right;
            }
        }
        return result;
    }

    //中序遍历
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode pop = stack.pop();
                result.add(pop.val);
                cur = pop.right;
            }
        }
        return result;
    }

    //后序遍历
    public static List<Integer> postTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        TreeNode pop = null;//最近一次弹栈的元素
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == pop) {
                    pop = stack.pop();
                    ans.add(pop.val);
                } else {
                    cur = peek.right;
                }
            }
        }
        return ans;
    }

    //模板遍历
    public static void modelTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        TreeNode pop = null;//最近一次弹栈的元素
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                //待处理左子树
                //前序遍历的话就在这里打印了
                printFormat("前序遍历" + cur.val, 32);
                cur = cur.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null) {
                    printFormat("中序遍历" + peek.val, 31);
                    //没有右子树
                    pop = stack.pop();
                    //后序遍历添加的值
                    printFormat("后序遍历" + peek.val, 34);
                } else if (peek.right == pop) {
                    //右子树已经被处理过
                    pop = stack.pop();
                    //后序遍历添加的值
                    printFormat("后序遍历" + peek.val, 34);
                } else {
                    //中序遍历时添加
                    printFormat("中序遍历" + peek.val, 31);
                    //去处理右子树
                    cur = peek.right;
                }
            }
        }

    }

    private static void printFormat(String s) {
        System.out.println(s + "\t");
    }

    public static void printFormat(String s, int color) {
        System.out.printf("\033[%dm%s\033[0m%n", color, s);
    }
}
